import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.Queue;

public class TestHeap {
    public int[] elem;
    public int usesize;


    public TestHeap() {
        
        this.elem =new int[10];
    }

    public void initHeap(int[] array)
    {
        for (int i = 0; i < array.length; i++) {
            elem[i]=array[i];
            usesize++;
        }
    }
    //大根堆
    //时间复杂度O（n）
    public void  createHeap()
    {
        for (int parent = (usesize-1-1)/2; parent >=0 ; parent--) {
            shiftDown(parent,usesize);
        }
    }

    public void shiftDown(int parent,int len)
    {
        int child=2*parent+1;
        while(child<len)
        {
            if(child+1<len && elem[child]<elem[child+1]) {
                child++;
            }
            if(elem[child]>elem[parent]) {
                int tmp = elem[parent];
                elem[parent] = elem[child];
                elem[child] = tmp;
                parent = child;
                child = 2 * parent + 1;
            }
            else
            {
                break;
            }
        }
    }
    //小根堆
    //时间复杂度O（n）
    public void  createHeap1()
    {
        for (int parent = (usesize-1-1)/2; parent >=0 ; parent--) {
            shiftDown1(parent,usesize);
        }
    }

    public void shiftDown1(int parent,int len)
    {
        int child=2*parent+1;
        while(child<len)
        {
            if(child+1<len && elem[child]>elem[child+1]) {
                child++;
            }
            if(elem[child]<elem[parent]) {
                int tmp = elem[parent];
                elem[parent] = elem[child];
                elem[child] = tmp;
                parent = child;
                child = 2 * parent + 1;
            }
            else
            {
                break;
            }
        }
    }

    public void shiftUp(int child)
    {
        int parent=(child-1)/2;
        while(child>0)
        {
           if(elem[child]>elem[parent])
           {
               int tmp=elem[child];
               elem[child]=elem[parent];
               elem[parent]=tmp;

               child=parent;
               parent=(child-1)/2;
           }
           else
           {
               break;
           }

        }

    }

    //时间复杂度 n*log(N)
    public void offer(int val)
    {
        if(ifFull())
        {
            elem= Arrays.copyOf(elem,2*elem.length);
        }

        elem[usesize++]=val;

        shiftUp(usesize-1);
    }
    public boolean ifFull()
    {
        return elem.length==usesize;
    }

    //删除数据
    public void pop()
    {
        if(isEmpty())
        {
            return ;
        }

        int tmp=elem[0];
        elem[0]=elem[usesize-1];
        elem[usesize-1]=tmp;
        shiftDown(0,usesize--);
    }

    public boolean isEmpty()
    {
        return usesize==0;
    }


    //交换
    public void swap(int i,int j)
    {
        int tmp=elem[i];
        elem[i]=elem[j];
        elem[j]=tmp;
    }
    /*
    时间复杂度O(n*logN)
    空间复杂度O(1)
     */
    //升序建立大根堆
    //降序建立小根堆
    public void headsort()
    {
        int end=usesize-1;
        while(end>0)
        {
            swap(0,end);
            shiftDown(0,end);
            end--;
        }

    }
}

